import java.util.HashMap;
import java.util.HashSet;

/**
 * @version Create on 2012-11-11
 * @author Yinzi Chen
 */

public class MinimumWindowSubstring {

	public String minWindow(String S, String T) {
		int n = S.length(), m = T.length();
		if (n < m || m == 0)
			return "";
		HashMap<Character, Integer> map = new HashMap<Character, Integer>();
		HashMap<Character, Integer> need = new HashMap<Character, Integer>();
		for (int i = 0; i < m; ++i) {
			if (need.containsKey(T.charAt(i)))
				need.put(T.charAt(i), need.get(T.charAt(i)) + 1);
			else
				need.put(T.charAt(i), 1);
		}
		int[] q = new int[n];
		int head = 0, rear = -1;
		String s = "";
		int cnt = 0;
		HashSet<Character> visit = new HashSet<Character>();
		for (int i = 0; i < n; ++i) {
			if (need.containsKey(S.charAt(i))) {
				if (map.containsKey(S.charAt(i))) {
					map.put(S.charAt(i), map.get(S.charAt(i)) + 1);
				} else {
					map.put(S.charAt(i), 1);
				}
				if (map.get(S.charAt(i)) >= need.get(S.charAt(i))
						&& !visit.contains(S.charAt(i))) {
					visit.add(S.charAt(i));
					cnt++;
				}
				while (head <= rear
						&& map.get(S.charAt(q[head])) > need.get(S
								.charAt(q[head]))) {
					map.put(S.charAt(q[head]), map.get(S.charAt(q[head])) - 1);
					head++;
				}
				q[++rear] = i;
				if (cnt == need.size()
						&& (s.equals("") || s.length() > i + 1 - q[head])) {
					s = S.substring(q[head], i + 1);
				}
			}
		}
		return s;
	}

	public static void main(String[] args) {
	}
}
